#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/2 23:24
# @USER    : Shengji He
# @File    : LongestCommonPrefix.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        """
        Write a function to find the longest common prefix string amongst an array of strings.
        If there is no common prefix, return an empty string "".

        :param strs: List[str]
        :return: str

        Example 1:
            Input: ["flower","flow","flight"]

            Output: "fl"

        Example 2:
            Input: ["dog","racecar","car"]

            Output: ""

            Explanation: There is no common prefix among the input strings.

        Note:
            All given inputs are in lowercase letters a-z.
        """
        output = ''
        for cmplst in zip(*map(list, strs)):
            old = ''.join(cmplst)
            if old[0] * len(old) == old:
                output += old[0]
            else:
                break
        return output


if __name__ == '__main__':
    S = Solution()
    num = ["flower", "flow", "flight"]
    print(S.longestCommonPrefix(num))
    print('done')
